package leetcode_121_140;

import java.util.*;

public class findLadders_126 {
    /**
     *详细题目要求见leetcode
     * @param beginWord 起始单词 1 <= length <= 5
     * @param endWord 目标单词
     * @param wordList 字典
     * @return 最短转换序列
     */
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        /**
         * 初步思路是，遍历字典
         * 使用集合统计并保存字典的每一个单词对应只相差一个字母的其他对应字符串
         * 暴力递归判断
         * 超时了，只通过19个用例，虽然时间复杂度不行，代码也很繁杂，好歹也算一种解法
         * 去看高解
         * 发现竟然有很多也跑不完全部用例
         */
        List<Integer>[]one=new ArrayList[wordList.size()];
        for(int t=0;t<wordList.size();t++)
            one[t]=new ArrayList<>();
        List<Integer>begin_one=new ArrayList<>();  //beginWord可以变换的单词下标

        //添加每一个单词可以进行转换的单词下标集合
        for(int t=0;t<wordList.size();t++){
           if(isOne(beginWord,wordList.get(t)))
               begin_one.add(t);

            for (int i = t+1; i < wordList.size(); i++) {
                if (isOne(wordList.get(t), wordList.get(i))){
                    one[t].add(i);
                    one[i].add(t);
                }
            }
        }

        //计算出所有可能
        for(int t=0;t<begin_one.size();t++){
            path.add(begin_one.get(t));
            function(begin_one.get(t),endWord,wordList,one);
            path.remove(path.size()-1);
        }

        //下标转化为单词
        List<List<String>>Ans=new ArrayList<>();
        for(List<Integer>list:ans){
            List<String>stringList=new ArrayList<>();
            stringList.add(beginWord);
            for(int i:list)
                stringList.add(wordList.get(i));
            Ans.add(stringList);
        }
        return Ans;
    }
    List<List<Integer>>ans=new ArrayList<>();

    List<Integer>path=new ArrayList<>(); //使用下标表示实时路径，为了避免路径检查中的equals方法

    int minPath=Integer.MAX_VALUE;       //实时最短路径长度
    void function(int beginWord,String endWord, List<String> wordList,List<Integer>[]one){
        if(wordList.get(beginWord).equals(endWord)){  //如果此时已经变换完成，返回
            List<Integer>result=new ArrayList<>(path);  //不影响实时路径
            if (path.size() == minPath)  //和之前的最短路径相等，直接添加
                ans.add(result);
            else{                    //是更短的路径，清空ans，再添加
                ans.clear();
                ans.add(result);
            }
            minPath = result.size();
            return;
        }
        for(int i=0;i<one[beginWord].size();i++){  //遍历beginword可以变换的所有单词
            //不可以与路径中已经有的单词重复
            int count=0;
            for (int s:path)
                if(s==one[beginWord].get(i)) {
                    count++;
                }
            if (count != 1){
                if(path.size()+1>minPath)//如果再加上单词已经超过了之前的最短路径直接返回
                    return;
                path.add(one[beginWord].get(i));
                function(one[beginWord].get(i), endWord, wordList, one);
                path.remove(path.size()-1);
            }
        }
    }
    /**
     * 判断两个单词是否只相差一个字母
     * @return
     */
    public boolean isOne(String s1,String s2){
        int count=0;
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)!=s2.charAt(i))
                count++;
            if(count>1)
                return false;
        }
        return true;
    }


    /**
     * 高解17ms
     * 广度优先遍历构造无向图 + 深度优先遍历找到所有解
     * 解法详细说明 https://leetcode.cn/problems/word-ladder-ii/solutions/277612/yan-du-you-xian-bian-li-shuang-xiang-yan-du-you--2/
     */
    public List<List<String>> findLadders2(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        // 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入哈希表，这里命名为「字典」
        Set<String> dict = new HashSet<>(wordList);
        // 特殊用例判断
        if (!dict.contains(endWord)) {
            return res;
        }
        // 因为从 beginWord 开始扩展，因此 dict 里一定不可以有 beginWord
        dict.remove(beginWord);

        // 第 1 步：广度优先遍历构建图
        // 为了避免记录不需要的边，我们需要记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先遍历的第几层
        // steps 记录了已经访问过的 word 集合，同时记录了在第几层访问到
        Map<String, Integer> steps = new HashMap<>();
        steps.put(beginWord, 0);
        // 记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系，dfs 的时候会用到
        Map<String, Set<String>> from = new HashMap<>();
        boolean found = bfs(beginWord, endWord, dict, steps, from);

        // 第 2 步：深度优先遍历找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部
        if (found) {
            Deque<String> path = new ArrayDeque<>();
            path.add(endWord);
            dfs(from, path, beginWord, endWord, res);
        }
        return res;
    }


    /**
     * 广度优先遍历构造无向图
     * @param dict 单词字典
     * @param steps steps 记录了已经访问过的 word 集合，同时记录了在第几层访问到
     * @param from  记录了单词是从哪些单词扩展而来
     */
    private boolean bfs(String beginWord, String endWord, Set<String> dict, Map<String, Integer> steps, Map<String, Set<String>> from) {
        int wordLen = beginWord.length();
        int step = 0;
        boolean found = false;

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            //处理当前所在层的单词，寻找他们可变化的未记录过的单词，组成下一层
            for (int i = 0; i < size; i++) {
                String currWord = queue.poll();
                char[] charArray = currWord.toCharArray();

                //遍历所有更换当前单词的一位字母变换成的单词，寻找字典中是否存在
                //这样处理是因为hashSet存储，查找更快，如果样本量很大，一个一个判断字典中的单词会很慢
                for (int j = 0; j < wordLen; j++) {
                    char origin = charArray[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        // 将每一位替换成 26 个小写英文字母
                        charArray[j] = c;
                        String nextWord = String.valueOf(charArray);

                        //如果已经访问过，跳过该新单词
                        // 注意：这几行代码的逻辑先后顺序
                        if (steps.containsKey(nextWord) && steps.get(nextWord) == step) {
                            from.get(nextWord).add(currWord);
                        }

                        //如果字典中不包含该新单词，跳过
                        if (!dict.contains(nextWord)) {
                            continue;
                        }

                        dict.remove(nextWord);

                        // dict 和 steps 承担了已经访问的功能
                        queue.offer(nextWord);

                        // 维护 from、steps、found 的定义
                        from.putIfAbsent(nextWord, new HashSet<>());  //将nexWord由currWord变化而来记录起来
                        from.get(nextWord).add(currWord);
                        steps.put(nextWord, step);
                        if (nextWord.equals(endWord)) {
                            // 注意：由于有多条路径到达 endWord 找到以后不能立即退出，只需要设置 found = true 即可
                            found = true;
                        }
                    }
                    charArray[j] = origin;
                }
            }
            if (found) {
                break;
            }
        }
        return found;
    }

    private void dfs(Map<String, Set<String>> from, Deque<String> path, String beginWord, String cur, List<List<String>> res) {
        if (cur.equals(beginWord)) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (String precursor : from.get(cur)) {
            path.addFirst(precursor);
            dfs(from, path, beginWord, precursor, res);
            path.removeFirst();
        }
    }




    /**
     *类似上一题，但是这题只需要返回长度
     * 所以构建好第一条路径时就可以直接返回长度
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        // 特殊用例判断
        if (!dict.contains(endWord)) {
            return 0;
        }
        // 因为从 beginWord 开始扩展，因此 dict 里一定不可以有 beginWord
        dict.remove(beginWord);

        //广度优先遍历构建图
        Map<String, Integer> steps = new HashMap<>();
        steps.put(beginWord, 0);
        return bfs2(beginWord, endWord, dict, steps);
    }


    /**
     * 广度优先遍历构造无向图
     * @param dict 单词字典
     * @param steps steps 记录了已经访问过的 word 集合，同时记录了在第几层访问到
     */
    private int bfs2(String beginWord, String endWord, Set<String> dict, Map<String, Integer> steps) {
        int wordLen = beginWord.length();
        int step = 0;

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);

        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            //处理当前所在层的单词，寻找他们可变化的未记录过的单词，组成下一层
            for (int i = 0; i < size; i++) {
                String currWord = queue.poll();
                char[] charArray = currWord.toCharArray();

                for (int j = 0; j < wordLen; j++) {
                    char origin = charArray[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        // 将每一位替换成 26 个小写英文字母
                        charArray[j] = c;
                        String nextWord = String.valueOf(charArray);

                        //如果已经访问过，跳过该新单词
                        // 注意：这几行代码的逻辑先后顺序
                        if (steps.containsKey(nextWord) && steps.get(nextWord) == step) {
                            continue;
                        }

                        //如果字典中不包含该新单词，跳过
                        if (!dict.contains(nextWord)) {
                            continue;
                        }

                        dict.remove(nextWord);

                        // dict 和 steps 承担了已经访问的功能
                        queue.offer(nextWord);

                        steps.put(nextWord, step);

                        if (nextWord.equals(endWord)) {
                            // 注意：由于有多条路径到达 endWord 找到以后不能立即退出，只需要设置 found = true 即可
                            return step+1;
                        }
                    }
                    charArray[j] = origin;
                }
            }
        }
        return 0;
    }
}
